package LeetCode.month04.day102;

/**
 * @author 16778
 * @date 2025/11/12 9:44
 * @description
 */
public class No2654 {
    public int minOperations(int[] nums) {
        int n = nums.length;
        int cnt = 0;
        int gcdAll = 0;
        for (int num : nums) {
            gcdAll = gcd(gcdAll,num);
            if(num==1) cnt++;
        }
        if(gcdAll!=1) return -1;
        if(cnt>0) return n-cnt;
        int min = n;
        for (int i = 0; i < n; i++) {
            int g = nums[i];
            for (int j = i+1; j < n; j++) {
                g = gcd(g,nums[j]);
                if(g == 1){
                    min = Math.min(min,j-i);
                    break;
                }
            }
        }
        return min+n-1;
    }

    public int gcd(int x,int y){
        while(x!=0){
            int temp = x;
            x = y%x;
            y = temp;
        }
        return y;
    }
}
